This invention relates to an improvement in a vector correlation detecting circuit for a movement detection at a compression of moving image, and more particularly relates to a circuit for detecting which region of an image in a previous frame a given region of an observed image in a present frame is the most similar to.
Explained first is about a memory processing of a moving image data.
FIG. 6 shows an example of a moving image data. One screen, i.e. one frame is composed of 720.times.480 picture elements. The image moves by displaying 30 frames per second. One picture element is composed of 8 bits and indicates the luminance thereof. The image data has such a construction, so that, for example, a memory capacity of 10.times.60.times.30.times.720.times.480.times.8=49,766,400,000 bits is required for recording 10-minute image data.
As a result, such a voluminous image data requires much time for transferring, storing and editing the data, and involves excessive cost in a hardware. In order to attack the problem, the image data is compressed to reduce the time and cost.
FIGS. 7, 8(a), 8(b) and 9 show an example of the image data compression. The compression method in the figures uses correlation between frames. As shown in FIG. 7, utilizing that an image of a one-frame previous frame is similar to a present frame, a finite difference of the image data between the one-frame previous frame and the present frame is extract to reduce data.
In order to further compress the data, an image region which is most similar to an observed image region is searched, namely the movement detection is carried out. The movement detection is ordinarily carried out per macro block. The macro block means, as shown in FIG. 8(a), a micro section into which the frame is divided, and is ordinarily composed of 16.times.16 picture elements. Wherein, the movement detection is carried out, as shown in FIG. 8(b), in such a manner that at the calculation of finite difference between a given macro block of the present frame and that of the previous frame, a block whose finite difference is smaller is searched around the macro block to obtain a further smaller finite difference data. A search region around the macro block is ordinarily composed of about 48.times.48 picture elements.
The above movement detection is carried out, for example, considering that an image region is a vector having components whose number is the number of picture elements, and a correlation between the image regions is a correlation of two vectors. The correlation of the two vectors is measured per micro block, using a scale S expressed by a formula (1), and an image region the scale S of which is the smallest is judged as the most similar region. ##EQU1## X: data within macro block of frame to be compressed Y: data within macro block of previous frame
Xi: i-th component of data X PA1 Yi: i-th component of data Y
By such a movement detection, the finite difference data is made further smaller, as shown in FIG. 9.
The above calculation is repeated 32.times.32=1024 times within the search region. For every macro block this operation is repeated 45.times.30=1350 times, thus the processing per one frame is completed. 10.times.60.times.30.times.1350=24,300,000 times calculations are required for 10-minute image data processing.
In this way, the movement detection requires the repetition of the large amount of calculations, which consumes much time. Therefore, speed-up of a basic operation of the calculator is desired in order to reduce the calculation time.
A parallel operation of the calculators is considered for improving the calculation processing. In so doing, however, a considerable number of calculators must be arranged, so that the hardware increases in its area as a whole. The size reduction of hardware of the basic calculator is desired since the size reduction thereof is effective for an image processing system as a whole though the reduced area is slight.
FIG. 10 schematically shows a predictor utilizing the movement detection. In the figure, reference numeral 51 indicates a present frame. 52 is an observed image region in the present frame 51. 53 is a previous frame. 54 is a search region in the previous frame 53. 55 is an image region which is the most similar to the observed region 54 in the search region 54. As described before, for the prediction using the movement detection, the most similar region is searched first in the previous frame 53 with respect to the observed image region 52. Normally the search is conducted in the image region 54 around the part corresponding to the observed image region 52. Next, after the most similar region 55 is determined, the finite difference between the search region 54 and the observed image region 52 is calculated by a finite difference calculator 56, then the finite difference data is coded by an encoder 57 with orthogonal transform or the like.
Conventionally, for calculating the scale S with the formula (1), absolute values of Xi and Yi are calculated per components X, Y. The conventional methods are shown in FIGS. 11 and 12.
A conventional vector correlation detecting circuit 1 in FIG. 11 is explained first. In the figure, reference numerals 61 and 62 designate corresponding component data Xi, Yi of two sets of N-dimensional vector data (X1, X2, . . . , XN), (Y1, Y2, . . . , YN). 63 and 64 are subtracters. 65 is a multiplexer. 66 is an accumulator. In the method in FIG. 11, the subtracters 63, 64 perform respective subtractions (Xi-Yi) and (Yi-Xi) for the corresponding component data Xi 61, Yi 62 of the two sets of N-dimensional vector data (X1, X2, . . . , XN), (Y1, Y2, . . . , YN). The multiplexer 65 selects one, which is positive, of two results of subtractions to obtain a value of .vertline.Xi-Yi.vertline.. The accumulator 66 accumulates the value thereof as "i" is increased.
Next, the conventional vector correlation detecting circuit 2 in FIG. 12 is explained. In the figure, reference numerals 71 and 72 designate, as well as the above, corresponding component data Xi, Yi of two sets of N-dimensional vector data (X1, X2, . . . , XN), (Y1, Y2, . . . , YN). 73 is a subtracter. 74 is a bit inversion circuit. 75 is an adder. 76 is a multiplexer. 77 is an accumulator. In the correlation detecting circuit in FIG. 12, the subtracter 73 performs a subtraction (Xi-Yi) for input data Xi 71, Yi 72 of the two sets of N-dimensional vector data (X1, X2, . . . , XN), (1, Y2, . . . , YN). The result of subtraction (Xi-Yi) is directly outputted when the result of subtraction is positive, and a calculation processing for 2's complement notation expressed by a formula (2) is carried out when the result of subtraction is negative. EQU .vertline.Xi-Yi.vertline.= (Xi-Yi)+1 (2)
Namely, after bits of Xi-Yi are inverted by the bit inversion circuit 74, 1 is added by the adder 75 to output data of (Xi-Yi)+1. Wherein, " " means a bit inversion. Obtaining a value of .vertline.Xi-Yi.vertline., the value is accumulated by the accumulator 77 as "i" is increased.
FIG. 13 shows another conventional vector correlation detecting circuit 3. In the figure, reference numerals 81 and 82 indicate two sets of N-dimensional vector data (X1, X2, . . . , XN), (Y1, Y2, . . . , YN). 83 is subtracter. 84 is a bit inversion circuit for inverting bits of a result of subtraction which is obtained by the subtracter 83. 85 is a multiplexer for selecting the result of subtraction or the result of subtraction through the bit inversion circuit 84. 86 is a counter for counting the number of result of subtraction, whose value is negative, obtained by the subtracter 83. 87 is an accumulator. 88 is an adder.
In the vector correlation detecting circuit 3, the subtracter 83 performs a subtraction (Xi-Yi) per each corresponding components of the two N-dimensional vector data 81 (X1, X2, . . . , XN), 82 (Y1, Y2, . . . , YN). The multiplexer 85 selects the data (Xi-Yi) directly when the result of subtraction is positive, and selects a bit-inverted data (Xi-Yi) when the result of subtraction is negative so as to obtain data whose number is N. The counter 86 counts the number of cases where the result of subtraction is negative. The adder 88 adds the N data and the value of the counter 86 to obtain a correlation value of the vector.
The principal of the calculation is: EQU .vertline.Xi-Yi.vertline.= (Xi-Yi)+1
when the value of (Xi-Yi) is negative at the calculation of .vertline.Xi-Yi.vertline.. Wherein, the counter 86 counts the number of "+1" of the last item at the right side, then the counted result is added to a whole added result.
However, the vector correlation detecting circuit 1 in FIG. 11 needs the two subtracters for obtaining one absolute value, which requires a large number of elements. In the vector correlation detecting circuit in FIG. 12, there cause carries from a least significant bit to a most significant bit at a stage of adding 1. This requires much time for each calculation of absolute value. Moreover, the conventional example shown in FIG. 13 requires the counter and the adder, which increases the elements in number and calculation time by processing time for adding the value of the counter to the adder.